package org.example;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class algorithm_Demo4 {
    public static void main(String[] args) {
        //快速排序
        int []arr={6,1,2,7,9,3,4,5,10,8};
        quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }

    }
    public static void quickSort(int []arr,int i,int j) {
        int start=i;
        int end=j;
        int baseNumber=arr[i];
        //递归出口
        //start == end：这种情况意味着子数组中只有一个元素。单个元素的数组本身就是有序的，无需再进行排序，所以直接返回。
        //start > end：这种情况表示子数组为空，即没有元素需要排序，同样直接返回。
        if (start>=end){
            return;
        }
        while(start!=end){
            while(true){
                if (end<=start||arr[end]<baseNumber) {
                    break;
                }
                end--;
            }
            while(true){
                if (end<=start||arr[start]>baseNumber) {
                    break;
                }
                start++;
            }
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
        }
        int temp=arr[i];
        arr[i]=arr[start];
        arr[start]=temp;

        //左边
        quickSort(arr,i,start-1);
        //右边
        quickSort(arr,start+1,j);
    }
}
